package com.wwlwxg.algorithm.list;

import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class LinkedList<E> implements Iterable<E> {

	transient int size = 0;
	transient Node<E> first;
	transient Node<E> last;

	public LinkedList() {
	}

	/**
	 * 添加元素，作为头元素
	 * @param e
	 */
	private void linkFirst(E e) {
		Node<E> f = first;
		Node<E> newNode = new Node<E>(null, e, f);
		first = newNode;
		if(f == null) {
			last = newNode;
		} else {
			f.prev = newNode;
		}
		size++;
	}

	/**
	 * 添加元素，作为最后一个元素
	 */
	void linkLast(E e) {
		Node<E> l = last;
		Node<E> newNode = new Node<E>(l, e, null);
		last = newNode;
		if(l == null) {
			first = newNode;
		} else {
			l.next = newNode;
		}
		size ++;
	}

	/**
	 * Inserts element e before non-null Node succ.
	 */
	void linkBefore(E e, Node<E> succ) {
		final Node<E> prev = succ.prev;
		final Node<E> newNode = new Node<E>(prev, e, succ);
		succ.prev = newNode;
		if(prev == null) {
			first = newNode;
		} else {
			prev.next = newNode;
		}
		size++;
	}

	/**
	 * Unlinks non-null first node f.
	 */
	private E unlinkFirst(Node<E> f) {
		final E element = f.item;
		final Node<E> next = f.next;
		f.next = null;
		f.item = null;
		first = next;
		if(next == null) {
			last = null;
		} else {
			next.prev = null;
		}
		size--;
		return element;
	}

	private E unlinkLast(Node<E> l) {
		final Node<E> prev = l.prev;
		final E item = l.item;
		l.prev = null;
		l.item = null;
		last = prev;
		if(prev == null) {
			first = null;
		} else {
			prev.next = null;
		}
		size--;

		return item;
	}

	E unlink(Node<E> x) {
		final E item = x.item;
		final Node<E> prev = x.prev;
		final Node<E> next = x.next;
		x.prev = null;
		x.next = null;
		x.item = null;
		if(prev == null) {
			first = next;
		} else {
			prev.next = next;
		}

		if(next == null) {
			last = prev;
		} else {
			next.prev = prev;
		}

		return item;
	}

	public E getFirst() {
		final Node<E> node = first;
		if(node == null) {
			throw new NoSuchElementException();
		}
		return node.item;
	}

	public E getLast() {
		final Node<E> node = last;
		if(node == null) {
			throw new NoSuchElementException();
		}
		return node.item;
	}

	public E removeFirst() {
		final Node<E> f = first;
		if(f == null) {
			throw new NoSuchElementException();
		}
		return unlinkFirst(f);
	}

	public E removeLast() {
		final Node<E> l = last;
		if(l == null) {
			throw new NoSuchElementException();
		}
		return unlinkLast(l);
	}

	public void addFirst(E e) {
		linkFirst(e);
	}

	public void addLast(E e) {
		linkLast(e);
	}

	public int size() {
		return size;
	}

	public boolean add(E e) {
		linkLast(e);
		return true;
	}

	public boolean remove(E e) {
		if(e == null) {
			for(Node<E> node = first; node != null; node = node.next) {
				if(node.item == null) {
					unlink(node);
					return true;
				}
			}
		} else {
			for(Node<E> node = first; node != null; node = node.next) {
				if(e.equals(node.item)) {
					unlink(node);
					return true;
				}
			}
		}

		return false;
	}

	public void clear() {
		for(Node<E> x = first; x != null;) {
			Node<E> next = x.next;
			x.next = null;
			x.prev = null;
			x.item = null;
			x = next;
		}
		first = last = null;
		size = 0;
	}

	Node<E> node(int index) {
		if(index < (size >> 1)) {
			Node<E> f = first;
			for(int i = 0; i < index; i++) {
				f = f.next;
			}
			return f;
		} else {
			Node<E> l = last;
			for(int i = size - 1; i > index; i--) {
				l = l.prev;
			}
			return l;
		}
	}

	public int indexOf(E o) {
		int index = 0;
		if(o == null) {
			for(Node<E> node = first; node != null; node = node.next) {
				if(node.item == null) {
					return index;
				}
				index++;
			}
		} else {
			for(Node<E> node = first; node != null; node = node.next) {
				if(node.item.equals(o)) {
					return index;
				}
				index++;
			}
		}
		return -1;
	}

	public int lastIndexOf(E o) {
		int index = size;
		if(o == null) {
			for(Node<E> node = last; node != null; node = node.prev) {
				index--;
				if(node.item == null) {
					return index;
				}
			}
		} else {
			for(Node<E> node = last; node != null; node = node.prev) {
				index--;
				if(node.item.equals(o)) {
					return index;
				}
			}
		}
		return -1;
	}

	// TODO
	public boolean addAll(int index, Collection<? extends E> c) {
		return false;
	}

	// TODO
	public boolean addAll(Collection<? extends E> c) {
		return addAll(size, c);
	}

	// TODO
	public boolean contains(E o) {
		return indexOf(o) != -1;
	}

	/**
	 * 迭代器方法
	 * @return
	 */
	@Override
	public Iterator iterator() {
		return null;
	}

	private static class Node<E> {
		E item;
		Node<E> next;
		Node<E> prev;

		Node(Node<E> prev, E element, Node<E> next) {
			this.item = element;
			this.next = next;
			this.prev = prev;
		}
	}

	public static class ListNode {
		private ListNode pre;
		private Object data;
		private ListNode next;
	}

}
